/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 强仔
 * Date: 2022-11-05
 * Time: 12:27
 */
public class Main {

    // 背包问题 1
    // 一个物品放一次，找最多可以放多少容量
    public static int backPack(int m, int[] a) {
        int n = a.length;
        int[][] array = new int[n][m + 1];

        for (int i = 0; i <= m; i++) {
            if(i >= a[0]){
                array[0][i] = a[0];
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                if(a[i] > j){
                    array[i][j] = array[i - 1][j];
                } else {
                    array[i][j] = Math.max(array[i - 1][j], array[i - 1][j - a[i]] + a[i]);
                }
            }
        }

        return array[n - 1][m];
    }

    // 空间优化，一维数组
    public static int backPackI(int m, int[] a) {
        int n = a.length;
        int[] array = new int[m + 1];

        for (int i = 0; i <= m; i++) {
            if(i >= a[0]){
                array[i] = a[0];
            }
        }

        for (int i = 1; i < n; i++) {
            // 注意：此处 j 必须逆序遍历
            for (int j = m; j >= a[i]; j--) {
                array[j] = Math.max(array[j], array[j - a[i]] + a[i]);
            }
        }

        return array[m];
    }

    // 背包问题2
    // 一个物品放一次，找最大价值
    public static int backPackII(int m, int[] a, int[] v) {
        int n = a.length;
        int[][] array = new int[n][m + 1];

        for (int i = 0; i <= m; i++) {
            if(i >= a[0]){
                array[0][i] = v[0];
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                if(a[i] > j){
                    array[i][j] = array[i - 1][j];
                } else {
                    array[i][j] = Math.max(array[i - 1][j], array[i - 1][j - a[i]] + v[i]);
                }
            }
        }
        return array[n - 1][m];
    }

    // 背包问题3
    // 一个物品可以放无数次，找最大的价值
    public int backPackIII(int[] a, int[] v, int m) {
        int n = a.length;
        int[][] array = new int[n][m + 1];

        for (int i = 0; i <= m; i++) {
            int count = i / a[0];
            array[0][i] = count * v[0];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                if(a[i] > j){
                    array[i][j] = array[i - 1][j];
                } else {
                    array[i][j] = Math.max(array[i - 1][j], array[i][j - a[i]] + v[i]);
                }
            }
        }
        return array[n - 1][m];
    }

    public int backPackIII2(int[] a, int[] v, int m) {
        int n = a.length;
        int[] array = new int[m + 1];

        for (int i = 0; i <= m; i++) {
            int count = i / a[0];
            array[i] = count * v[0];
        }

        for (int i = 1; i < n; i++) {
            for (int j = i; j <= m; j++) {
                array[j] = Math.max(array[j], array[j - a[i]] + v[i]);
            }
        }
        return array[m];
    }

    public int backPackIII3(int[] a, int[] v, int m) {
        int n = a.length;
        int[] array = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = a[i - 1]; j <= m; j++) {
                array[j] = Math.max(array[j], array[j - a[i - 1]] + v[i - 1]);
            }
        }
        return array[m];
    }

    // 背包问题4
    // 一个物品可以放无数次，找正好放满的方案数
    public static int backPackIV(int[] nums, int target) {
        int n = nums.length;
        int[][] array = new int[n][target + 1];

        for (int i = 0; i <= target; i++) {
            if(nums[0] <= i && i % nums[0] == 0){
                array[0][i] = 1;
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= target; j++) {
                array[i][j] = array[i - 1][j];
                if(nums[i] == j){
                    array[i][j]++;
                } else if(nums[i] < j){
                    array[i][j] += array[i][j - nums[i]];
                }
            }
        }

        return array[n - 1][target];
    }


    public static int backPackIV2(int[] nums, int target) {
        int n = nums.length;
        int[] array = new int[target + 1];

        for (int i = 0; i <= target; i++) {
            if(nums[0] <= i && i % nums[0] == 0){
                array[i] = 1;
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = nums[i]; j <= target; j++) {
                if(nums[i] == j){
                    array[j]++;
                } else if(nums[i] < j){
                    array[j] += array[j - nums[i]];
                }
            }
        }

        return array[target];
    }

    public static int backPackIV3(int[] nums, int target) {
        int n = nums.length;
        int[] array = new int[target + 1];

        array[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = nums[i - 1]; j <= target; j++) {
                 if(nums[i - 1] <= j){
                    array[j] += array[j - nums[i - 1]];
                }
            }
        }

        return array[target];
    }

    // 背包问题5
    // 一个物品只能装一次，找正好的装满的方案数
    public int backPackV(int[] nums, int target) {
        int n = nums.length;
        int[][] array = new int[n][target + 1];

        for (int i = 0; i <= target; i++) {
            if(nums[0] == i){
                array[0][i] = 1;
                break;
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= target; j++) {
                array[i][j] = array[i - 1][j];
                if(nums[i] == j){
                    array[i][j]++;
                }
                if(nums[i] < j){
                    array[i][j] += array[i - 1][j - nums[i]];
                }
            }
        }

        return array[n - 1][target];
    }

    public int backPackV2(int[] nums, int target) {
        int n = nums.length;
        int[] array = new int[target + 1];

        array[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = target; j >= 0; j--) {
                if(nums[i - 1] <= j){
                    array[j] += array[j - nums[i - 1]];
                }
            }
        }
        return array[target];
    }

    // 416. 分割等和子集
    public boolean canPartition(int[] nums) {
        int val = 0;
        for (int num : nums) {
            val += num;
        }

        // 总和是奇数无法分割
        if(val % 2 == 1){
            return false;
        }

        // 要达到的目标值，即背包的容量；数组 nums 就是各个物品的重量
        int target = val / 2;

        boolean[] array = new boolean[target + 1];
        for (int i = 0; i <= target; i++) {
            if(nums[0] == i){
                array[i] = true;
            }
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = target; j >= 0; j--) {
                if(nums[i] <= j){
                    array[j] = array[j] || array[j - nums[i]];
                }
            }
        }

        return array[target];
    }


    // 474. 一和零
    static class Space{
        public int zero;
        public int one;

        public Space(int zero, int one) {
            this.zero = zero;
            this.one = one;
        }
    }

    // 474. 一和零
    public static int findMaxFormI(String[] strs, int m, int n) {
        int len = strs.length;
        int[] ones = new int[len];     // 记录每个字符串中 1 的个数
        int[] zeros = new int[len];     // 记录每个字符串中 0 的个数

        for (int i = 0; i < len; i++) {
            String s = strs[i];
            int c1 = 0;
            int c2 = 0;
            for (char ch : s.toCharArray()) {
                if (ch == '1') {
                    c1++;
                } else {
                    c2++;
                }
            }
            ones[i] = c1;
            zeros[i] = c2;
        }

        Space[] spaces = new Space[(m + 1) * (n + 1)];
        int index = 0;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                Space space = new Space(i, j);
                spaces[index++] = space;
            }
        }

        int[][] array = new int[len][spaces.length];
        for (int i = 0; i < spaces.length; i++) {
            Space space = spaces[i];
            if (space.zero >= zeros[0] && space.one >= ones[0]) {
                array[0][i] = 1;
            }
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < spaces.length; j++) {
                Space space = spaces[j];
                if (space.zero < zeros[i] || space.one < ones[i]) {
                    array[i][j] = array[i - 1][j];
                } else {
                    array[i][j] = Math.max(array[i - 1][j], array[i - 1][j - (zeros[i] * (n + 1) + ones[i])] + 1);
                }
            }
        }

        return array[len - 1][spaces.length - 1];
    }



    public static int findMaxFormII(String[] strs, int m, int n) {
        int len = strs.length;
        int[] ones = new int[len];     // 记录每个字符串中 1 的个数
        int[] zeros = new int[len];     // 记录每个字符串中 0 的个数

        for (int i = 0; i < len; i++) {
            String s = strs[i];
            for (char ch : s.toCharArray()) {
                if(ch == '1'){
                    ones[i]++;
                } else {
                    zeros[i]++;
                }
            }
        }

        int col = (m + 1) * (n + 1);

        int[][] array = new int[len][col];
        for (int i = 0; i < col; i++) {
            int sz = i/(n + 1);
            int so = i%(n + 1);
            if( sz >= zeros[0] && so >= ones[0]){
                array[0][i] = 1;
            }
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < col; j++) {
                int sz = j/(n + 1);
                int so = j%(n + 1);
                if(sz < zeros[i] || so < ones[i]){
                    array[i][j] = array[i - 1][j];
                } else {
                    array[i][j] = Math.max(array[i - 1][j], array[i - 1][j - (zeros[i] * (n + 1) + ones[i])] + 1);
                }
            }
        }

        return array[len - 1][col - 1];
    }


    // 三维数组处理 0和1问题

    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] array = new int[len + 1][m + 1][n + 1];

        for (int i = 1; i <= len; i++) {
            // count[0] 表示 str[i - 1] 中 0 的数量；count[1] 表示 str[i - 1]中 1 的数量
            int[] count = countZeroAndOne(strs[i - 1]);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    array[i][j][k] = array[i - 1][j][k];
                    if(count[0] <= j && count[1] <= k){
                        array[i][j][k] = Math.max(array[i - 1][j][k], array[i - 1][j - count[0]][k - count[1]] + 1);
                    }
                }
            }
        }
        return array[len][m][n];
    }

    private int[] countZeroAndOne(String s) {
        int[] count = new int[2];
        for (char ch : s.toCharArray()) {
            count[ch - '0']++;
        }
        return count;
    }

    // 目标和
    public static int findTargetSumWays(int[] nums, int target) {
        target = Math.abs(target);

        int val = 0;
        for (int num : nums) {
            val += num;
        }

        int[][] array = new int[nums.length][val*2 + 1];
        for (int i = -val; i <= val; i++) {
            if (Math.abs(i) == nums[0]) {
                if (nums[0] == 0) {
                    // -0 = 0，+0 = 0
                    array[0][i + val] = 2;
                } else {
                    array[0][i + val] = 1;
                }
            }
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = -val; j <= val; j++) {
                if(j - nums[i] >= -val){
                    array[i][j + val] += array[i - 1][j - nums[i] + val];
                }
                if(j + nums[i] <= val){
                    array[i][j + val] += array[i - 1][j + nums[i] + val];
                }
            }
        }

        return array[nums.length - 1][target + val];
    }

    // 322. 零钱兑换
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] array = new int[n][amount + 1];

        for (int i = 0; i <= amount; i++) {
            if(i % coins[0] == 0){
                array[0][i] = i / coins[0];
            } else {
                array[0][i] = -1;
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= amount; j++) {
                array[i][j] = array[i - 1][j];
                if(coins[i] <= j && array[i][j - coins[i]] != -1){
                    if(array[i - 1][j] == -1){
                        array[i][j] = array[i][j - coins[i]] + 1;
                    } else {
                        array[i][j] = Math.min(array[i - 1][j], array[i][j - coins[i]] + 1);
                    }
                }
            }
        }

        return array[n - 1][amount];
    }


    public int coinChangeII(int[] coins, int amount) {
        int n = coins.length;
        int[] array = new int[amount + 1];

        for (int i = 1; i <= amount; i++) {
            array[i] = -1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = coins[i - 1]; j <= amount; j++) {
                if(array[j - coins[i - 1]] != -1){
                    if(array[j] == -1){
                        array[j] = array[j - coins[i - 1]] + 1;
                    } else {
                        array[j] = Math.min(array[j], array[j - coins[i - 1]] + 1);
                    }
                }
            }
        }

        return array[amount];
    }


    // 518. 零钱兑换 II
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] array = new int[n + 1][amount + 1];

        array[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                array[i][j] = array[i - 1][j];
                if(j > coins[i - 1]){
                    array[i][j] += array[i][j - coins[i]];
                }
            }
        }

        return array[n][amount];
    }

    public static void main(String[] args) {
        int[] a = {2, 3, 5, 7};
        int m = 12;
        System.out.println(backPack(m, a));
    }
}
